A typical search engine indexing algorithm utilizes an inverted index data structure. This is conceptually similar to the index in the back of a book; it is an index data structure mapping content, such as a list of words, to its location in a document (or set of documents). In the context of a search engine, the documents are commonly web pages, e-mail messages, and the like. The occurrence of a word in a document may be called a posting, and the list of all documents containing a word may be called a posting list. Just as a book index entry lists page numbers, a posting list may contain document identification numbers (DocIDs). When a search engine receives a query, it can look up the posting list for each word in the query and combine the results. In order to combine the results efficiently, the postings may be stored in order of their DocIDs.
It may be desirable to store posting lists in as little space as possible. By using the differences between adjacent DocIDs rather than the DocIDs themselves, the postings can contain smaller numbers. However, once a posting list has been generated and the differences between adjacent DocIDs are determined, it can be computationally costly to adjust or modify the sequence of DocIDs. Posting lists may not be readable while being updated and computational resources must be used to constantly update posting lists with updated deltas as documents are modified and subsequently are added or deleted from the posting list. Traditionally, additional posting lists may be generated to keep track of modifications to the original posting list. However, this requires two or more searches of posting lists for any term leading to more latency related to a search query. Accordingly, there is a need to improve the computational performance of incorporating modifications of documents in encoded posting lists.